/*
 * To change this template, choose Tools | Templates and open the template in
 * the editor.
 */
package Towers;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 *
 * @author asc
 */
public class Towers
{

    /**
     * @param args the command line arguments
     */
    
    static casilla[][] tablero;
    int tamanyo;
    boolean debug = false;  //muestra los conjuntos de factibles y sus cambios [A]ntes-[D]espues
    boolean debug2 = false; //muestra las restricciones en la salida
    boolean debug3 = false; //muestra el tablero en cada transicion
    
    public void parse(String fichero){
        try
        {
            
            BufferedReader entrada = new BufferedReader(new InputStreamReader(new FileInputStream(fichero), "UTF-8"));
            tamanyo = Integer.decode(entrada.readLine());
            if(debug)System.out.print(String.valueOf(tamanyo) + "\n");
            tablero = new casilla[tamanyo+2][tamanyo+2];
            String[] linea; 
                    
            for (int i = 1; i < tamanyo+1; i++)
            {
                linea = entrada.readLine().split(" ");
                for (int j = 1; j < tamanyo+1; j++)
                {
                    tablero[i][j] = new casilla(i,j,Integer.decode(linea[j-1]));
                }
            }
            
            linea = entrada.readLine().split(" ");
            for (int j = 1; j < tamanyo+1; j++)
            {
                tablero[0][j] = new casilla (0,j,Integer.decode(linea[j-1]));
            }
            linea = entrada.readLine().split(" ");
            for (int j = 1; j < tamanyo+1; j++)
            {
                tablero[j][0] = new casilla (j,0,Integer.decode(linea[j-1]));
            }
            linea = entrada.readLine().split(" ");
            for (int j = 1; j < tamanyo+1; j++)
            {
                tablero[j][tamanyo+1] = new casilla(j,tamanyo+1,Integer.decode(linea[j-1]));
            }
            linea = entrada.readLine().split(" ");
            for (int j = 1; j < tamanyo+1; j++)
            {
                tablero[tamanyo+1][j] = new casilla(tamanyo+1,j,Integer.decode(linea[j-1]));
            }
            tablero[0][0] = new casilla(0,0,0);
            tablero[tamanyo+1][tamanyo+1] = new casilla(0,0,0);
            tablero[tamanyo+1][0] = new casilla(0,0,0);
            tablero[0][tamanyo+1] = new casilla(0,0,0);
            /*
             * 
             * Eliminar factibles resultantes de los valores inicializados
             * alguna OP mas
             * 
             */
            for (int i = 1; i < tamanyo+1; i++)
            {
                for (int j = 1; j < tamanyo+1; j++)
                {
                    if(tablero[i][j].getValor()>0){
                        for(int k = 1; k<tamanyo+1; k++)tablero[k][j].elimiarFactible(tablero[i][j].getValor());
                    }
                    if(tablero[i][j].getValor()>0){
                        for(int k = 1; k<tamanyo+1; k++)tablero[i][k].elimiarFactible(tablero[i][j].getValor());
                    }
                }
            }
            if(debug2)imprimeTablero2();
        }
        catch (IOException ex)
        {
            Logger.getLogger(Towers.class.getName()).log(Level.SEVERE, null, ex);
        }
        
    }
    public void imprimeTablero2(){
        for (int i = 0; i < tamanyo+2; i++)
        {
            for (int j = 0; j < tamanyo+2; j++)
            {
                System.out.print(tablero[i][j].getValor() + "\t");
            }
            System.out.print("\n");
        }
        System.out.print("\n");
    }
    
    public void imprimeTablero(){
        for (int i = 1; i <= tamanyo; i++)
        {
            for (int j = 1; j <= tamanyo; j++)
            {
                System.out.print(tablero[i][j].getValor() + " ");
            }
            System.out.print("\n");
        }
        System.out.print("\n");
    }
    public class casilla{
        int posicionX;
        int posicionY;
        Integer valor;
        Boolean asignado;
        LinkedList<Integer> factibles;
        HashMap<Integer, Integer> podados;

        public casilla(int posicionX, int posicionY, Integer valor)
        {
            this.posicionX = posicionX;
            this.posicionY = posicionY;
            this.valor = valor;
            asignado=(valor>0)?true:false;
            factibles = new LinkedList<Integer>();
            podados = new HashMap<Integer, Integer>();
            if(!asignado)genFactibles();
        }

        public casilla(int valor) {
            this.valor = valor;
            factibles = new LinkedList<Integer>();
            podados = new HashMap<Integer, Integer>();
            genFactibles();
        }
        
        private void genFactibles(){
            for (int i = 1; i <= tamanyo; i++) {
                if(valor != i)factibles.add(i);
            }
        }
        
        Boolean elimiarFactible(Integer i){
            if(debug)System.out.print("A-["+posicionX + "," + posicionY + "]: "+i +"| "+ factibles + "\n");
            Boolean X=factibles.remove(i);
            if(debug)System.out.print("D-["+posicionX + "," + posicionY + "]: "+i +"| "+ factibles + "\n");
            return X;
        }
        void anyadirPodados(int causanteX, int causanteY, Integer podado){
            podados.put((Integer)(causanteX * tamanyo + causanteY),podado);
            
        }
        Boolean responsableFiltrado(Integer causanteX, Integer causanteY){
            return podados.get((Integer)(causanteX * tamanyo + causanteY))!=null;
        }
        
        Integer eliminarPodados(int causanteX, int causanteY){
            return podados.remove((Integer)(causanteX * tamanyo + causanteY));
        }
        
        Boolean anyadirFactibles(Integer podado){
            
            if(!factibles.contains(podado))factibles.add(podado);
            Collections.sort(factibles);
            return true;
        }
        
        Boolean cumpleRestriccion(Integer a){
            if(asignado)return true;
            if(factibles.size()>1)return true;
            if(factibles.size()==1 && !factibles.contains(a))return true;
            return false;
        }
        
        Boolean esConsistente(){
            if(debug)System.out.print("Comprobar izquierda\n" + posicionX + ":" + posicionY + " " + tablero[posicionX][tamanyo+1].getValor() +"\n");
            int maxLocal=0;
            int edificios=tablero[posicionX][0].getValor();
            for(int i=1; i<=posicionY; i++){
                if(valor == tablero[posicionX][i].getValor() && i!=posicionY)return false;
                if(debug)System.out.print(posicionX + "-" + i +":"+ tablero[posicionX][i].getValor() + "\t" + maxLocal + "-" + edificios + "\n");
                if(Math.max(maxLocal, tablero[posicionX][i].getValor())!=maxLocal){
                    maxLocal=tablero[posicionX][i].getValor();
                    edificios--;
                }
                if(edificios<0 || (maxLocal==tamanyo && edificios!=0))return false;
            }
            if(debug)System.out.print("Comprobar arriba\n" + posicionX + ":" + posicionY + " " + tablero[posicionX][tamanyo+1].getValor() +"\n");
            maxLocal=0;
            edificios=tablero[0][posicionY].getValor();
            for(int i=1; i<=posicionX; i++){
                if(valor == tablero[i][posicionY].getValor() && i!=posicionX)return false;
                if(debug)System.out.print(i + "-" + posicionY + ":"+ tablero[i][posicionY].getValor() + "\t" + maxLocal + "-" + edificios + "\n");
                if(Math.max(maxLocal, tablero[i][posicionY].getValor())!=maxLocal){
                    maxLocal=tablero[i][posicionY].getValor();
                    edificios--;
                }
                if(edificios<0 || (maxLocal==tamanyo && edificios!=0))return false;
            }
            
            if(posicionX==tamanyo){
                if(debug)System.out.print("Comprobar abajo\n" + posicionX + ":" + posicionY + " " + tablero[posicionX][tamanyo+1].getValor() +"\n");
                maxLocal=0;
                edificios=tablero[tamanyo+1][posicionY].getValor();
                for(int i=tamanyo; i>0; i--){
                    if(debug)System.out.print(i + "-" + posicionY + ":"+ tablero[i][posicionY].getValor() + "\t" + maxLocal + "-" + edificios + "\n");
                    if(Math.max(maxLocal, tablero[i][posicionY].getValor())!=maxLocal){
                        maxLocal=tablero[i][posicionY].getValor();
                        edificios--;
                    }
                    if(edificios<0)return false;
                }
                if(edificios != 0)return false;
            }
            
            if(posicionY==tamanyo){
                if(debug)System.out.print("Comprobar derecha\n" + posicionX + ":" + posicionY + " " + tablero[tamanyo+1][posicionY].getValor() +"\n");
                maxLocal=0;
                edificios=tablero[posicionX][tamanyo+1].getValor();
                for(int i=tamanyo; i>0; i--){
                    if(debug)System.out.print(posicionX + "-" + i +":"+ tablero[posicionX][i].getValor() + "\t" + maxLocal + "-" + edificios + "\n");
                    if(Math.max(maxLocal, tablero[posicionX][i].getValor())!=maxLocal){
                        maxLocal=tablero[posicionX][i].getValor();
                        edificios--;
                    }
                    if(edificios<0)return false;
                }
                if(edificios != 0)return false;
            }
            
            return true;
        }
        
        int tamanyoFactibles(){
            return factibles.size();
        }
        
        int kFactible(int k){
            return factibles.get(k);
        }

        public void setValor(Integer valor)
        {
            this.valor = valor;
        }

        public Integer getValor()
        {
            return valor;
        }

        public Boolean getAsignado()
        {
            return asignado;
        }
        
    }
    
    public Boolean FC (int i , int j){
        if(!tablero[i][j].getAsignado()){
            for (int k = 0; k < tablero[i][j].tamanyoFactibles(); k++)    //a ∈ factibles[i] hacer
            {
                if(debug)System.out.print("[" + i + "," + j +"] " + tablero[i][j].kFactible(k) + "\n");
                tablero[i][j].setValor(tablero[i][j].kFactible(k)); //Xi = a;
                if(debug3)imprimeTablero2();
                if(tablero[i][j].esConsistente()){
                    if (i == tamanyo && j==tamanyo){ //solución
                        return true;
                    }
                    else //if(tablero[i][j].esConsistente())
                    {
                        if(forward (i, j ,tablero[i][j].kFactible(k))){
                            if(j<tamanyo){
                                if(FC(i, j+1)){
                                    return true;
                                }
                            }
                            else{
                                if(FC(i+1, 1)){
                                    return true;
                                }
                            }
                        }
                        Restaurar (i,j);
                    }
                }
            }
            tablero[i][j].setValor(0);
            return false;
        }
        else{
            if(tablero[i][j].esConsistente()){
                if(i==tamanyo && j==tamanyo) return true;
                
                if(j<tamanyo){
                    if(FC(i, j+1)){
                        return true;
                    }
                }
                else{
                    if(FC(i+1, 1)){
                        return true;
                    }
                }
            }
            return false;
        }
    }
    
    public Boolean forward(int i, int j, int  a){ 
        
        if(debug)System.out.print("Fila\n");
        for (int k = j+1; k <= tamanyo; k++)    //para toda j=i+1 hasta N hacer
        {
            //Boolean vacio = true;
            //for (int l = 0; l < tablero[k][j].getFactibles().size(); l++)  //para cada b ∈ factibles[j] hacer
            //{
                if(!tablero[i][k].cumpleRestriccion(a)){ //(a,b) pertenece Rij
                    //vacio = false;
                    return false;
                }
                else{
                    if(tablero[i][k].elimiarFactible(a)) //eliminar b de factible[j];
                        tablero[i][k].anyadirPodados(i,j,a); //Añadir b a podado[j];
                }
            //}
            //if (vacio)
            //{
            //    return false;
            //}
        }
        if(debug)System.out.print("Columna\n");        
        for (int k = i+1; k <= tamanyo; k++)    //para toda j=i+1 hasta N hacer
        {
            //Boolean vacio = true;
            //for (int l = 0; l < tablero[k][j].getFactibles().size(); l++)  //para cada b ∈ factibles[j] hacer
            //{
                if(!tablero[k][j].cumpleRestriccion(a)){ //(a,b) pertenece Rij
                    //vacio = false;
                    return false;
                }
                else{
                    if(tablero[k][j].elimiarFactible(a)) //eliminar b de factible[j];
                        tablero[k][j].anyadirPodados(i,j,a); //Añadir b a podado[j];
                }
            //}
            //if (vacio)
            //{
            //    return false;
            //}
        }
        return true;
     }
    
     public void Restaurar(int i, int j){
         
        for (int k = j+1; k <= tamanyo; k++){ //para toda j=i+1 hasta N hacer
            //for (int l = 0; l < 10; l++)//para todo b ∈ podado[j] hacer
            //{
                if (tablero[i][k].responsableFiltrado(i, j))//si Xi responsable filtrado b
                {
                    //tablero[k][j].eliminarPodados(i, j);//Eliminar b de podado[j]
                    tablero[i][k].anyadirFactibles(tablero[i][k].eliminarPodados(i, j)); //Añadir b a factible[j]
                }
            //}
        }
        for (int k = i+1; k <= tamanyo; k++){ //para toda j=i+1 hasta N hacer
            //for (int l = 0; l < 10; l++)//para todo b ∈ podado[j] hacer
            //{
                if (tablero[k][j].responsableFiltrado(i, j))//si Xi responsable filtrado b
                {
                    //tablero[k][j].eliminarPodados(i, j);//Eliminar b de podado[j]
                    tablero[k][j].anyadirFactibles(tablero[k][j].eliminarPodados(i, j)); //Añadir b a factible[j]
                }
            //}
        }
    }
    
    public static void main(String[] args)
    {
        boolean debug3=false; //pasan todos los tableros de golpe
        if(debug3){
            //String[] entrada ={"principiante1.txt" , "principiante2.txt" , "principiante3.txt" , "facil1.txt" , "facil2.txt" , "normal1.txt" , "normal2.txt" , "dificil1.txt" , "dificil2.txt"};
            String[] entrada = {"extremo.txt" , "extremo2.txt"};
            for (int i = 0; i < entrada.length; i++)
            {
               Towers juego = new Towers();
                if(juego.debug2)System.out.print(entrada[i]+"\n");
                juego.parse(entrada[i]);
                if(!juego.FC(1, 1)) System.out.print("ERROR\n");
                if(!juego.debug2)juego.imprimeTablero();
                else juego.imprimeTablero2();
            }
        }
        else{
            Towers juego = new Towers();
            if(juego.debug2)System.out.print(args[0]+"\n");
            juego.parse(args[0]);
            if(juego.FC(1, 1))
                if(!juego.debug2)juego.imprimeTablero();
                else juego.imprimeTablero2();
        }
    }
}
